package org.example;

/**
 * 42. 接雨水
 */
public class Trap {

    public int trap(int[] height) {
        int ans = 0;
        if (height == null || height.length == 0) {
            return 0;
        }
        int l = 0, r = height.length - 1;
        int leftMax = 0, rightMax = 0;
        while (r > l) {
            if (height[l] < height[r]) {
                if (height[l] > leftMax) {
                    leftMax = height[l];
                } else {
                    ans += leftMax - height[l];
                }
                l++;
            } else {
                if (height[r] > rightMax) {
                    rightMax = height[r];
                } else {
                    ans += rightMax - height[r];
                }
                r--;
            }
        }
        return ans;
    }


    public int trapKimi(int[] height) {
        if (height == null || height.length == 0) {
            return 0;
        }

        int left = 0, right = height.length - 1; // 初始化左右指针
        int leftMax = 0, rightMax = 0; // 初始化左右最大高度
        int ans = 0; // 初始化答案变量，用于累计存水量

        while (left < right) {
            if (height[left] < height[right]) {
                // 当左边的高度小于右边的高度时
                if (height[left] >= leftMax) {
                    // 更新左边的最大高度
                    leftMax = height[left];
                } else {
                    // 计算当前位置可以接的雨水量，并累加到答案中
                    ans += leftMax - height[left];
                }
                left++; // 移动左指针
            } else {
                // 当右边的高度小于或等于左边的高度时
                if (height[right] >= rightMax) {
                    // 更新右边的最大高度
                    rightMax = height[right];
                } else {
                    // 计算当前位置可以接的雨水量，并累加到答案中
                    ans += rightMax - height[right];
                }
                right--; // 移动右指针
            }
        }
        return ans; // 返回累计的存水量
    }
}
